package com.arron.algorithm.leetcodetop100.滑动窗口;

import com.arron.algorithm.leetcodetop100.前缀和.最大子数组和_前缀和;
import com.arron.algorithm.leetcodetop100.动态规划.子序列or子数组.最大子数组和_动态规划;

/**
 * 53. 最大子数组和 ,
 */
public class 最大子数组和 {


    /**
     * 也可以用前缀和，或者动态规划做
     *  @see  最大子数组和_前缀和
     *   @see 最大子数组和_动态规划
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        if (nums.length<2){
            return nums[0];
        }
        int left = 0;
        int right = 0;

        int windowSum = 0;

        int maxSum=Integer.MIN_VALUE;
//]
        while (right<nums.length){

            windowSum+=nums[right];
            right++;
            maxSum = Math.max(windowSum,maxSum);

            //扩大窗口
            while (left<right && windowSum<0){

                windowSum-=nums[left];
                left++;
            }
        }
        return maxSum;
    }

    public static void main(String[] args) {
        最大子数组和 maxArraySum = new 最大子数组和();

        int[] nums = new int[]{-2,1,-3,4,-1,2,1,-5,4};
        maxArraySum.maxSubArray(nums);

    }


}
